package com.atguigu.stack;

/**
 * 栈实现综合计算器
 * 要求满足的规则:
 * 1. 数字为任意位的整数
 * 2. 符号包含+ - * / , 但不包含()
 *
 * 关于通常算法思考的思路:
 * 顺序推衍思路. 与全局推衍思路的差别在于:
 * 前者按照正常思考的顺序一点一点儿将细节搭起来, 优点是方案的效率通常较高, 缺点是速度较慢(因为需要根据细节一点一点思考),
 * 通常适合先从简单的案例出发, 得出一个满足初级要求的方案, 再将要求的复杂度逐步提升, 最后得到初始要求的解决方案. 很明细, 这样虽然步步为营, 但所需时间较长.
 * 后者则先不考虑细节, 而从大局上先确定大致方案的步骤, 再将实现步骤的细节逐步填充.
 * 优点是需要时间较短, 且思考复杂度易管理, 缺点则是很难一次得到比较完美的方案, 只能先得到一个可行的方案.
 *
 * 本问题按照教程来做, 相当于是顺序推衍.
 * 先考虑简单的案例, 即数字均为个位数字. 这种情况不必考虑多位字符串转数字的问题.
 * 从最开始遍历各个字符.
 * 1. 遇到数字, 放到数字池中. 此时数字池的数据结构暂不确定
 * 2. 遇到符号, 并不能马上将当前数字和后面的数字拿出来计算, 因为可能有优先级的问题, 需要先看看后面的符号是什么样的.
 * 2.1 如果后面的符号比当前符号的优先级高, 则当前符号先存储起来备用, 使用顺序一定晚于后面的符号. 此处即可推测, 符号的存储使用栈可能较为合适
 * 2.2 如果后面的符号, 与当前符号的优先级相等, 则当前符号就可以先出结果了. 且将之前的结果也逆序结算出来.
 * 2.3 如果后面的符号, 优先级低于当前符号, 则同上.
 * 3. 由于符号使用栈的结构, 即先进先出, 所以数字池的数据结构也需要与之保持一致, 即也是栈
 *
 *
 */
public class CalculatorDemo {
    public static void main(String[] args) {
        /*
         * 1+2*3-4/2+5+6-1*3
         * 1+6-4/2+5+6-1*3
         *
         */
//        Calculator calculator = new Calculator("1+2*3-4/2+5+6-1*3");
//        Calculator calculator = new Calculator("1-2-3*2");
        Calculator calculator = new Calculator("7*2*2^2-5+11+5+3-4");
        int result = calculator.calcResult();
        System.out.println("result:"+result);
    }
}

class Calculator{
    private final String formula;

    public Calculator(String formula) {
        this.formula = formula;
    }

    public int calcResult(){
        ArrayStack2 numStack = new ArrayStack2(16);
        ArrayStack2 operStack = new ArrayStack2(16);
        StringBuilder cacheNum= new StringBuilder();
        for (char c : formula.toCharArray()) {
            if (OperationSignUtil.isOper(c)) {
                numStack.push(Integer.parseInt(cacheNum.toString()));
                cacheNum=new StringBuilder("");
                if (operStack.isEmpty()) {
                    operStack.push(c);
                }else{
                    char lastOper = (char) operStack.peek();
                    int curPriority = OperationSignUtil.priority(c);
                    int lastPriority = OperationSignUtil.priority(lastOper);
                    if (curPriority>lastPriority) {
                        operStack.push(c);
                    }else{
//                        operStack.pop();
//                        int num1 = numStack.pop();
//                        int num2 = numStack.pop();
//                        int calc = OperationSignUtil.calc(num1, num2, lastOper);
//                        numStack.push(calc);
                        // 不留同级. 此时必定可以保证, 符号栈的优先级是从低到高入栈的!!! 不存在同级的符号.
                        while(!operStack.isEmpty()){
                            int oper = operStack.pop();
                            int num1 = numStack.pop();
                            int num2 = numStack.pop();
                            int calc = OperationSignUtil.calc(num1, num2, (char) oper);
                            numStack.push(calc);
                        }
                        operStack.push(c);
                    }
                }
            }else{
                cacheNum.append(c-48);
//                numStack.push(c-48);
            }
        }
        numStack.push(Integer.parseInt(cacheNum.toString()));
        cacheNum.delete(0,cacheNum.length()-1);
        while(!operStack.isEmpty()){
            int oper = operStack.pop();
            int num1 = numStack.pop();
            int num2 = numStack.pop();
            int calc = OperationSignUtil.calc(num1, num2, (char) oper);
            numStack.push(calc);
        }

        return numStack.pop();
    }

}


class ArrayStack2{
    private final int maxSize;
    private final int[] stack;
    private int top=-1;

    public ArrayStack2(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new int[maxSize];
    }

    public boolean isFull(){
        return this.top==maxSize-1;
    }

    public boolean isEmpty(){
        return this.top==-1;
    }

    public void show(){
        if (isEmpty()) {
            System.out.println("栈空...");
            return;
        }
        for (int i = this.top; i >= 0; i--) {
            System.out.printf("stack[%d]=%d\n",i,stack[i]);
        }
    }

    public void push(int val){
        if (isFull()) {
            System.out.println("栈满...");
            return;
        }
        this.stack[++this.top]=val;
    }

    public int pop(){
        if (isEmpty()) {
            throw new RuntimeException("栈空...");
        }

        return this.stack[this.top--];
    }

    public int peek(){
        if (isEmpty()) {
            throw new RuntimeException("栈空");
        }
        return this.stack[this.top];
    }
}

class OperationSignUtil{public static boolean isOper(char c){
    return c=='+'||c=='-'||c=='*'||c=='/'||c=='^';
}

    public static int priority(char c){
        switch (c){
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            case '^':
                return 3;
            default:
                throw new RuntimeException("不支持的符号");
        }
    }

    public static int calc(int num1,int num2,char oper){
        switch (oper){
            case '+':
                return num1+num2;
            case '-':
                return num2-num1;
            case '*':
                return num1*num2;
            case '/':
                return num2/num1;
            case '^':
                int cache=1;
                for (int i = 0; i < num1; i++) {
                    cache=cache*num2;
                }
                return cache;
            default:
                throw new RuntimeException("不支持的符号");
        }
    }

}

